//Paulo Kaique Paiva Brasil - 347203
//Victor Temoteo Pinto - 347220

#include <math.h>
#include <time.h>
#include <stdio.h>
#include <string.h>

    int comp;                                                                   //numero de comparacoes que um certo algoritmo executou
    int trocas;                                                                 //numero de trocas que um certo algoritmo executou
    char tipo;                                                                  //retorna o tipo do arquivo;
    char* name;                                                                 //nome do arquivo que está sendo lido;
    
    int number;                                                                 //número de palavras
    int size;                                                                   //tamanho das palavras
    
    char **original;
    char **lista;                                                               //vetor com as palavras do arquivo que o algoritmo ordenará
    
    
char* nomeArq(int x)
{
    int i=1;
    char* nome;
    nome = (char *)malloc(30*sizeof(char));
    
    FILE *sortlist;
    
    sortlist = fopen ("instances/sortlist", "r");
    
    if(sortlist==NULL){
        printf("\n** Erro na leitura do arquivo **\n");
        getchar();
        exit(1);
    }
    else{
        while( i<=x && !(feof(sortlist)) ){                                     //continua até o x-ésimo elemento ou até o final do arquivo
            fscanf(sortlist, "%s", nome);
            i++;
        }
        
        if( feof(sortlist) ){
            printf("\n** Erro: Atingido o final do arquivo **\n");
            getchar();
            exit(1);
        }
        
        fclose(sortlist);
        
        tipo = nome[10];
        name = (char *)malloc(30*sizeof(char));
        strcpy(name, &nome[10]);
        
        return(nome);
    }
}

void leitura(int x)
{
    FILE *arq;
    int i, j;
    
    arq = fopen( nomeArq(x), "r" );
    
    if (arq == NULL){
        printf ("\n** Erro na leitura do arquivo **\n");
        getchar();
        exit(1);
    }
    else{
        fscanf(arq, "%d", &number);
        fscanf(arq, "%d", &size);
        
        original = (char**) malloc(number*sizeof(char*));
        lista = (char**) malloc(number*sizeof(char*));
        
        if ( (lista == NULL) || (original == NULL) ) {
            printf ("\n** Erro: Memoria Insuficiente **");
            getchar();
            exit(1);
            }
        for(i = 0; i < number; i++){
            original[i] = (char*) malloc( (size+1)*sizeof(char) );
            lista[i] = (char*) malloc( (size+1)*sizeof(char) );
            if ( (lista[i] == NULL) || (original[i] == NULL) ) {
                printf ("** Erro: Memoria Insuficiente **");
                getchar();
                exit(i);
            }
        }
        
        i=0;
        do{
            fscanf(arq, "%s", original[i]);
            strcpy(lista[i], original[i]);
            i++;
        }while( i<number && !feof(arq) );
        
    }

    fclose(arq);
}

int comparar (char* A, char* B)
{
    int n, i=0, x=0;
    n = strlen(A);
    
    while( ( i<n-1 ) && (A[i] == B[i]) ) i++;                                   //Pela comparação, se as palavras forem iguais, retorna-se 0

    if (A[i] < B[i]) x = -1;                                                    //No caso de A ser menor que B, retorna -1
    if (A[i] > B[i]) x = 1;                                                     //No caso de A ser maior que B, retorna 1
   
    return (x);
}

void restaurar()                                                                //Funcao que restaura 'lista' para os valores originais
{                                                                               //para rodar outra funcao em cima de 'lista'
    int i, j;
    
    for(i=0; i<number; i++){
        strcpy(lista[i], original[i]);
    }
}

//ALGORITMOS DE ORDENAÇÃO

/* SELECTION SORT */
void selecao()
{
    trocas = 0; comp = 0;
    
    int i, j, min;
    char aux[size];
    
    for (i=0;i<number-1;i++){
        min = i;
        for (j=i+1;j<number;j++){
            comp++;
            if ( comparar (lista[min], lista[j]) == 1){
                min = j;
            }
        }
        trocas++;
        strcpy(aux, lista[i]);
        strcpy(lista[i], lista[min]);
        strcpy(lista[min], aux);
    }
}

/* INSERTION SORT */
void insercao()
{
    trocas = 0; comp = 0;
    
    int i, j, k;
    char aux[size];
    
    for (i=1;i<number;i++){
        j=0;
        while ( (j != i) && ( comparar(lista[i], lista[j]) != 1 ) ){
            comp++;
            strcpy (aux, lista[i]);
            k = i;
            while ( k != j){
                trocas++;
                strcpy (lista[k],lista[k-1]);
                k--;
            }
            trocas++;
            strcpy (lista[j], aux);
            j++;
        }
    }
}

/* HEAP SORT*/
void descer (int i){
      int max;
      char aux[size];
      comp++;
      if (i <= number/2){
            comp++;
            if ( (2*i)+1 > number){
                  max = 2*i;
            }else{
                  comp++;
                  if( comparar (lista[2*i], lista[(2*i)+1]) == +1 ){
                        max = 2*i;
                  }else{
                        max = (2*i)+1;
                  }
                  comp++;
                  if( comparar(lista[i], lista[max]) == -1 ){
                        trocas++;
                        strcpy (aux, lista[max]);
                        strcpy (lista[max], lista[i]);
                        strcpy (lista[i], aux);
                        descer (max);
                  }
            }
      }
}

void subir (int i){
    char aux[size];
    comp++;
    if (i > 1){
        comp++;
        if (comparar (lista[i], lista[i/2]) == +1){
            trocas++;
            strcpy (aux, lista[i]);
            strcpy (lista[i], lista[i/2]);
            strcpy (lista[i/2], aux);
            subir (i/2);
        }
    }
}

void extrair(){
    char aux[size];
    comp++;
    if(number>0){
        trocas++;
        strcpy (aux, lista[0]);
        strcpy (lista[0], lista[number]);
        strcpy (lista[number], aux);
        number--;
        descer(0);
    }
}

void construir(){
    int i;
    for ( i=number/2; i>=1; i-- ){
        descer (i);
    }
}

void heapsort (){
    trocas = 0; comp = 0;
    
    int i;
    i = number;
    number--;
    while (number>0){
        comp++;
        extrair();
    }
    number = i;
}

/* QUICK SORT*/
int particao (int a, int b){
    int p=a, t=a, i, j;
    char aux[size];
    for (i=a+1;i<=b;i++){
        comp++;
        if( comparar(lista[i], lista[p]) <= 0 ){
            trocas++;
            strcpy(aux, lista[i]);
            strcpy(lista[i], lista[t]);
            strcpy(lista[t], aux);
            comp++;
            if (p==t){
                p = i;
            }
            t++;
        }
    }
    trocas++;
    strcpy(aux, lista[p]);
    strcpy(lista[p], lista[t]);
    strcpy(lista[t], aux);
    p=t;
    return(p);
}

void quicksort (int a, int b){
    int p;
    if(b-a>0){
        p = particao (a, b);
        quicksort(a, p-1);
        quicksort(p+1, b);
    }
}

/* MERGE SORT */
void mix (int a, int b){
    int i=a, j=((a+b)/2)+1, k=0;
    int tam = (b-a)+1;
    
    char **vet;
    vet = (char**) malloc( tam*sizeof(char*) );
    if ( vet == NULL ) {
        printf ("\n** Erro: Memoria Insuficiente **");
        getchar();
        exit(1);
    }
    for(i = 0; i < tam; i++){
        vet[i] = (char*) malloc( (size+1)*sizeof(char) );
        if ( vet[i] == NULL ) {
            printf ("** Erro: Memoria Insuficiente **");
            getchar();
            exit(i);
        }
    }
    
    j=0;
    for(i=a; i<=b; i++){
        strcpy(vet[j], lista[i]);
        j++;
    }
    
    k=0; i=0; j= ( ((b-a)/2)+1 );
    
    while ( (i <= (b-a)/2 ) && (j <= b-a ) ){
        comp++;
        if ( comparar (vet[i], vet[j]) <= -1){
            trocas++;
            strcpy(lista[a+k], vet[i]);
            i++;
        }else{
            trocas++;
            strcpy(lista[a+k], vet[j]);
            j++;
        }
        k++;
    }
    while (i <= (b-a)/2 ){
        comp++;
        trocas++;
        strcpy(lista[a+k], vet[i]);
        i++; k++;
    }
    while (j <= b-a ){
        comp++;
        trocas++;
        strcpy(lista[a+k], vet[j]);
        j++; k++;
    }
}

void mergesort (int a, int b){
    trocas = 0; comp = 0;
    
    if (b - a > 0){
        mergesort ( a, (a+b)/2 );
        mergesort ( ((a+b)/2)+1, b );
        mix (a, b);
    }
}

//ALGORITMO DE COMPARACAO ENTRE OS ACIMA CITADOS~~
void comparacao(FILE *arquivo, int x)
{
    clock_t start_time;
    double tempo;
    
    leitura(x);

    printf("Gerando os valores para o arquivo %s. Algoritmo:      Heap sort...\n", name );      //Chamada do heapsort
    heapsort();
    start_time = clock();
    
    tempo = (clock() - start_time) / (double)CLOCKS_PER_SEC;
    
    fprintf(arquivo, "\t\t%c \t%.3f \t\t%d \t\t%d", tipo, tempo, trocas, comp);
    
    restaurar();
    
    printf("Gerando os valores para o arquivo %s. Algoritmo:     Quick sort...\n", name );      //Chamada do quicksort
    
    start_time = clock();
    trocas=0; comp=0;
    quicksort(0, number-1);
    tempo = (clock() - start_time) / (double)CLOCKS_PER_SEC;
    
    fprintf(arquivo, "\t\t\t%.3f \t\t%d \t\t%d", tempo, trocas, comp);
    
    restaurar();
    
    printf("Gerando os valores para o arquivo %s. Algoritmo:     Merge sort...\n", name );      //Chamada do mergesort
    
    start_time = clock();
    mergesort(0, number-1);
    tempo = (clock() - start_time) / (double)CLOCKS_PER_SEC;
    
    fprintf(arquivo, "\t\t\t%.3f \t\t%d \t\t%d", tempo, trocas, comp);
    
    restaurar();
    
    printf("Gerando os valores para o arquivo %s. Algoritmo: Insertion sort...\n", name );      //Chamada do insertion sort
    
    start_time = clock();
    insercao();
    tempo = (clock() - start_time) / (double)CLOCKS_PER_SEC;
    
    fprintf(arquivo, "\t\t\t%.3f \t\t%d \t\t%d", tempo, trocas, comp);
    
    restaurar();
    
    printf("Gerando os valores para o arquivo %s. Algoritmo: Selection sort...\n\n", name );    //Chamada do selection sort
    
    start_time = clock();
    selecao();
    tempo = (clock() - start_time) / (double)CLOCKS_PER_SEC;
    
    fprintf(arquivo, "\t\t\t%.3f \t\t%d \t\t%d\n", tempo, trocas, comp);
}


//ALGORITMO QUE GERA O RELATORIO DE SAIDA
void relatorio()
{
    int i=0;
    double tempo;
    
    FILE *arquivo;
    arquivo = fopen("relatorio.txt", "w");
    
    fprintf(arquivo, "-- Relatorio - Algoritmos de Ordenacao --\n");
    fprintf(arquivo, "-- Autores: Victor Temoteo e Paulo Kaique Brasil --\n\n\n");
    fprintf(arquivo, "Algoritmos testados: Selecao, Insercao, Mistura, Quicksort, Heapsort\n");
    fprintf(arquivo, "Dados analisados: tempo de execucao, numero de comparacoes, numero de trocas\n\n\n");
    fprintf(arquivo, "Tabela de dados:\n\n");
    fprintf(arquivo, "\t\t\tHeapsort \t\t\t\t\t\tQuicksort \t\t\t\t\t\tMergesort \t\t\t\t\t\tInsercao \t\t\t\t\t\tSelecao\n");
    fprintf(arquivo, "\t\t\ttempo \t\ttrocas \t\tcomparacoes \t\ttempo \t\ttrocas \t\tcomparacoes \t\ttempo \t\ttrocas \t\tcomparacoes \t\ttempo \t\ttrocas \t\tcomparacoes \t\ttempo \t\ttrocas \t\tcomparacoes \n");
    
    while(i<112) {
        if(i%4 == 0){
            fprintf(arquivo, "%d \t%d\n", number, size);
        }
        comparacao(arquivo, i+1);
        i++;
    }
    
    fclose(arquivo);
}

int main(){
    int i;
    
    printf("-- Algoritmos de Ordenacao --\n\n");
    printf("Autores: Paulo Kaique e Victor Temoteo\n\n");
    printf("Pressione qualquer tecla para iniciar a geracao do relatorio...");
    getchar();
    
    relatorio();
    
    system("PAUSE");
    
    return(0);
}
